package com.spd.tree;
/**
 * 二叉搜索树，该示例假设元素都没有重复。
 * @author xianchao
 *
 */
public class BinarySearch {

	private int[] array;
	
	//数结构
	private TreeNode rootNode = new TreeNode();
	
	public TreeNode getRootNode() {
		return rootNode;
	}

	public void setRootNode(TreeNode rootNode) {
		this.rootNode = rootNode;
	}

	public void init(int[] array) {
		this.array = array;
	}
	
	/**
	 * 构建树
	 */
	public void createTree() {
		//用第一个值作为根，然后构建树，创建树的时候，添加一个标兵节点为根节点，让其左右孩子都指向真实的根，
		//真实的根指向该标兵节点。
		rootNode.setValue(array[0]);
		for(int i = 1; i < array.length; i++) {
			TreeNode treeNode = new TreeNode();
			treeNode.setValue(array[i]);
			addNode(rootNode, treeNode);
		}
		System.out.println(rootNode);
	}
	
	/**
	 * 查找，并打印查找的过程所遍历到的值
	 * @param value
	 */
	public TreeNode search(TreeNode itemNode, int value) {
		if(itemNode.getValue() == value || 
				itemNode == null) {
			System.out.print(value + " ");
			return itemNode;
		} 
		System.out.print(itemNode.getValue() + " ");
		if(itemNode.getValue() > value) {
			return search(itemNode.getLeft(), value);
		} else if(itemNode.getValue() < value) {
			return search(itemNode.getRight(), value);
		}
		return null;
	}
	
	/**
	 * 把itemNode添加到rootNode为根的二叉树上
	 * @param rootNode
	 * @param itemNode
	 */
	private void addNode(TreeNode rootNode, TreeNode itemNode) {
		//叶子节点
		TreeNode tempNode = rootNode;
		//tempNode的父节点
		TreeNode tempParentNode = rootNode;
		while(tempNode != null) {
			tempParentNode = tempNode;
			if(itemNode.getValue() < tempNode.getValue()) {
				tempNode = tempNode.getLeft();
			} else {
				tempNode = tempNode.getRight(); 
			}
		}
		if(tempParentNode.getValue() > itemNode.getValue()) {
			tempParentNode.setLeft(itemNode);
			itemNode.setP(tempParentNode);
		} else {
			tempParentNode.setRight(itemNode);
			itemNode.setP(tempParentNode);
		}
	}
	
	/**
	 * 查找最大节点、最小节点
	 * 最小节点，从根开始，一直查找左子节点，一直找到节点没有子节点为止。
	 * 最大节点，从根开始，一直查找右子节点，一直找到节点没有子节点为止。
	 */
	public void findMaxMin() {
		int min = -999, max = 999;
		TreeNode treeNode = rootNode.getLeft();
		while(treeNode.getLeft() != null) {
			treeNode = treeNode.getLeft();
		}
		min = treeNode.getValue();
		treeNode = rootNode.getRight();
		while(treeNode.getRight() != null) {
			treeNode = treeNode.getRight();
		}
		max = treeNode.getValue();
		System.out.println("min:" + min + ", max:" + max);
	}
	
	/**
	 * 查询指定元素的后继
	 * @param value
	 */
	public TreeNode findNext(int value) {
		//1. 如果节点没有左右子节点，并且它是左子数，那么它的后继就是他的父节点
		//2. 如果有右节点存在，则查找右节点的，然后查找右节点的最左子节点。
		//3. 如果节点没有右孩子节点，则一直往上找父节点，直到找到一个节点，这个节点是它的父节点的左孩子。
		//查找到value对应的节点
		TreeNode treeNode = search(rootNode, value);
		if(treeNode == null) {
			System.out.println(String.format("树中没有%d对应的节点", value));
			return null;
		}
		if(treeNode.getLeft() == null && treeNode.getRight() == null) {
			TreeNode pNode = treeNode.getP();
			if(pNode != null && pNode.getLeft() == treeNode) {
				System.out.println(String.format("%d的后继是%d", value, pNode.getValue()));
				return pNode;
			}
		}
		if(treeNode.getRight() != null) {
			TreeNode rightNode = treeNode.getRight();
			while(rightNode.getLeft() != null) {
				rightNode = rightNode.getLeft();
			}
			int next = rightNode.getValue();
			System.out.println(String.format("%d的后继是%d", value, next));
			return rightNode;
		} else if(treeNode.getRight() == null) {
			TreeNode pNode = treeNode.getP();
			while(pNode != null) {
				TreeNode ppNode = pNode.getP();
				if(ppNode != null && ppNode.getLeft() == pNode) {
					System.out.println(String.format("%d的后继是%d", value, ppNode.getValue()));
					return ppNode;
				} else {
					pNode = ppNode;
				}
			}
		}
		return null;
	}
	
	/**
	 * 查找指定元素的前驱
	 * @param value
	 */
	public void findPre(int value) {
		//1. 如果是右叶子节点，则它的父节点为它的前驱
		//2. 如果是左孩子节点，则一直往上找，找到节点，该节点是它的父节点的右子树
		//3. 非叶子，则找它的孩子节点的最右孩子节点
		TreeNode treeNode = search(rootNode, value);
		if(treeNode == null) {
			System.out.println(String.format("树中没有%d对应的节点", value));
			return;
		}
		if(treeNode.getLeft() == null && treeNode.getRight() == null) {
			//右孩子
			if(treeNode.getP() != null && treeNode.getP().getRight() == treeNode) {
				System.out.println(String.format("%d的前驱是%d", value, treeNode.getP().getValue()));
				return;
			}
			//左孩子
			if(treeNode.getP() != null && treeNode.getP().getLeft() == treeNode) {
				TreeNode pNode = treeNode.getP();
				while(pNode.getP() != null && pNode.getP().getRight() == pNode) {
					System.out.println(String.format("%d的前驱是%d", value, pNode.getValue()));
					return;
				}
			}
		}
		//3. 非叶子节点，左孩子的最右节点
		TreeNode leftNode = treeNode.getLeft();
		TreeNode rightNode = leftNode.getRight();
		TreeNode rightPNode = leftNode.getRight();
		while(rightNode != null) {
			rightPNode = rightNode;
			rightNode = rightNode.getRight();
		}
		System.out.println(String.format("%d的前驱是%d", value, rightPNode.getValue()));
		return;
	}
	
	/**
	 * 插入节点
	 * @param value
	 */
	public void insert(int value) {
		TreeNode insertNode = new TreeNode();
		insertNode.setValue(value);
		TreeNode treeNode = rootNode;
		while(treeNode != null) {
			int nodeValue = treeNode.getValue();
			if(nodeValue > value) {
				TreeNode leftNode = treeNode.getLeft();
				if(leftNode == null) {
					treeNode.setLeft(insertNode);
					insertNode.setP(treeNode);
					return;
				} else {
					treeNode = treeNode.getLeft();
				}
			} else {
				TreeNode rightNode = treeNode.getRight();
				if(rightNode == null) {
					treeNode.setRight(insertNode);
					insertNode.setP(treeNode);
					return;
				} else {
					treeNode = treeNode.getRight();
				}
			}
		}
	}
	
	/**
	 * 删除节点
	 * @param value
	 */
	public void delete(int value) {
		TreeNode deleteNode = search(rootNode, value);
		//1. 没有孩子节点，直接删除。
		if(deleteNode.getLeft() == null && deleteNode.getRight() == null) {
			TreeNode pNode = deleteNode.getP();
			if(pNode.getLeft() == deleteNode) {
				pNode.setLeft(null);
			} else if(pNode.getRight() == deleteNode) {
				pNode.setRight(null);
			}
			return;
		}
		//2. 只有一个孩子，把孩子提升到节点位置，然后删除。
		TreeNode leftNode = deleteNode.getLeft();
		TreeNode rightNode = deleteNode.getRight();
		TreeNode dpNode = deleteNode.getP();
		if(leftNode == null && rightNode != null) {
			rightNode.setP(deleteNode.getP());
			if(dpNode.getLeft() == deleteNode) {
				dpNode.setLeft(leftNode);
			} else {
				dpNode.setRight(leftNode);
			}
			return;
		} else if(leftNode != null && rightNode == null) {
			leftNode.setP(deleteNode.getP());
			if(dpNode.getLeft() == deleteNode){
				dpNode.setLeft(leftNode);
			} else {
				dpNode.setRight(leftNode);
			}
			return;
		}
		//3. 假设要删除的节点为z，z的后继为y，并且y是z的右孩子，则用y替换z即可。
		TreeNode nextNode = findNext(value);
		if(nextNode == null) {
			return;
		}
		if(deleteNode.getRight() == nextNode) {
			TreeNode pNode = deleteNode.getP();
			nextNode.setP(pNode);
			if(pNode.getLeft() == deleteNode) {
				pNode.setLeft(nextNode);
			} else if(pNode.getRight() == deleteNode) {
				pNode.setRight(nextNode);
			}
			return;
		} else {
			//4. 假设要删除的节点为z，z的后继为y，但y不是z的右孩子，则1）用y的右孩子x替换替换y，2）置y为r的双亲，
			// 3）置y为q的孩子。4）置y为l的双亲。参见《算法导论》中12章中图12-4中的描述
			//z : deleteNode、y:nextNode、x: xNode、 l: lNode, r: rNode,
			//对于删除节点为根节点的情况，要特殊处理一下。
			//TODO 考虑是否用哨兵来替代这种处理方式。
			TreeNode qNode = deleteNode.getP();
			TreeNode xNode = nextNode.getRight();
			TreeNode lNode = deleteNode.getLeft();
			TreeNode rNode = deleteNode.getRight();
			//1）
			if(xNode != null) {
				xNode.setP(rNode);
			}
			if(rNode.getLeft() == nextNode) {
				rNode.setLeft(xNode);
			} else if(rNode.getRight() == nextNode) {
				rNode.setRight(xNode);
			}
			//2）
			rNode.setP(nextNode);
			nextNode.setRight(rNode);
			//3）当删除节点为根节点的时候
			if(qNode != null) {
				if(qNode.getLeft() == deleteNode) {
					qNode.setLeft(nextNode);
				} else if(qNode.getRight() == deleteNode) {
					qNode.setRight(nextNode);
				}
				nextNode.setP(qNode);
			} 
			
			//4）
			nextNode.setLeft(lNode);
			lNode.setP(nextNode);
			if(qNode == null) {
				rootNode = nextNode;
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		BinarySearch binarySearch = new BinarySearch();
		int[] array = new int[]{15, 6, 3, 8, 2, 4, 7, 13, 9, 18, 17, 20};
		binarySearch.init(array);
		//创建树
		binarySearch.createTree();
		//查找值
//		binarySearch.search(binarySearch.getRootNode(), 3);
		//获取最大、最小节点
//		binarySearch.findMaxMin();
		//查找后继
//		binarySearch.findNext(20);
		//查找前驱
//		binarySearch.findPre(6);
		//插入节点
//		binarySearch.insert(5);
		//删除节点
		//测试删除节点为6的情况下，构造数组int[] array = new int[]{15, 6, 3, 8, 2, 4, 7, 13, 9, 18, 17, 20};
//		binarySearch.delete(6);
		binarySearch.delete(15);
	}
}


